TNotes.leetcode

Appearance

⏰0382. 链表随机节点【中等】

0382. 链表随机节点【中等】 ​

1. 📝 题目描述 ​

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样。

实现 Solution 类：

  • Solution(ListNode head) 使用整数数组初始化对象。
  • int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

示例：

img

txt
输入
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
输出
[null, 1, 3, 2, 2, 3]

解释
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // 返回 1
solution.getRandom(); // 返回 3
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 2
solution.getRandom(); // 返回 3
// getRandom() 方法应随机返回 1、2、3中的一个，每个元素被返回的概率相等。

提示：

  • 链表中的节点数在范围 [1, 10^4] 内
  • -10^4 <= Node.val <= 10^4
  • 至多调用 getRandom 方法 10^4 次

进阶：

  • 如果链表非常大且长度未知，该怎么处理？
  • 你能否在不使用额外空间的情况下解决此问题？

2. 🎯 s.1 - 蓄水池抽样 ​

c
typedef struct {
    struct ListNode* head;
} Solution;

Solution* solutionCreate(struct ListNode* head) {
    Solution* obj = (Solution*)malloc(sizeof(Solution));
    obj->head = head;
    return obj;
}

int solutionGetRandom(Solution* obj) {
    int res = 0, i = 1;
    struct ListNode* node = obj->head;
    while (node) {
        if (rand() % i == 0) res = node->val;
        node = node->next;
        i++;
    }
    return res;
}

void solutionFree(Solution* obj) { free(obj); }
js
/**
 * @param {ListNode} head
 */
var Solution = function (head) {
  this.head = head
}

/**
 * @return {number}
 */
Solution.prototype.getRandom = function () {
  let res = 0,
    i = 1,
    node = this.head
  while (node) {
    // 蓄水池抽样：以 1/i 的概率选中当前节点
    if (Math.random() < 1 / i) res = node.val
    node = node.next
    i++
  }
  return res
}
py
class Solution:
    def __init__(self, head: Optional[ListNode]):
        self.head = head

    def getRandom(self) -> int:
        res, i, node = 0, 1, self.head
        while node:
            if random.randint(1, i) == 1:
                res = node.val
            node = node.next
            i += 1
        return res
  • 时间复杂度：初始化 O(1)，getRandom O(n)
  • 空间复杂度：O(1)

算法思路：

  • 蓄水池抽样：遍历链表时，第 i 个节点以 1i 的概率被选中
  • 保证每个节点被选中的概率均为 1n